//题目:
// 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，
// 你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
// 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。
// 每个房子粉刷不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
// 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
// 请计算出粉刷完所有房子最少的花费成本。
#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;
//代码
class Solution 
{
    int ret=INT_MAX;
    vector<vector<int>> dp;//记录第i个位置选第j个颜色时，刷完最后一个房子所需要的最小金额
public:
    int dfs(const vector<vector<int>>& costs,int pos,int color)
    {
        if(pos==costs.size()) return 0;
        
        if(dp[pos][color]!=0) return dp[pos][color];//记忆功能

        int min_money=INT_MAX;//第pos位置，选择color颜色，所需的最小金额
        for(int i=0;i<3;i++)
        {
            if(i!=color)
                min_money=min(min_money,costs[pos][color]+dfs(costs,pos+1,i));
        }
        dp[pos][color]=min_money;//记忆存储
        return min_money;
    }
    int minCost(vector<vector<int>>& costs) 
    {
        //要求：1.相邻房子不重色  2.花费的成本最低
        //1.全排列————超时—————>优化————>记忆化搜索  √
        // dp.resize(costs.size(),vector<int>(3,0));
        // for(int i=0;i<3;i++)
        //     ret=min(ret,dfs(costs,0,i));
        // return ret;

        //2.动态规划
        //1.创建dp表————记录从初始位置到第(i,j)位置，所需的最小金额
        int m=costs.size();
        vector<vector<int>> dp(m,vector<int>(3,0));
        //2.初始化
        dp[0][0]=costs[0][0],dp[0][1]=costs[0][1],dp[0][2]=costs[0][2];
        //3.填表————动态转移方程：dp[i][j]=costs[i][j]+min(dp[i-1][j-1],dp[i-1][j+1]);
        for(int i=1;i<costs.size();i++)
        {
            for(int j=0;j<3;j++)
            {
                if(j==0)
                    dp[i][j]=costs[i][j]+min(dp[i-1][j+1],dp[i-1][j+2]);
                else if(j==1)
                    dp[i][j]=costs[i][j]+min(dp[i-1][j-1],dp[i-1][j+1]);
                else
                    dp[i][j]=costs[i][j]+min(dp[i-1][j-1],dp[i-1][j-2]);
            }
        }
        //4.确定返回值
        int ret1=dp[m-1][0]<dp[m-1][1]?dp[m-1][0]:dp[m-1][1];
        int ret2=dp[m-1][2];
        return ret1<ret2?ret1:ret2;
    }
};